/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/partition-array
   @Language: C++
   @Datetime: 16-02-09 08:20
   */

class Solution {
public:
	/** Tips: all elements < k are moved to the left; vice versa
	 * using two point: i=0 and j=end-1
	 * find first nums[i] who bigger than k
	 * find last nums[j] who less than k
	 * swap nums[i] and nums[j]
	 * continue loop
	 * */
	int partitionArray(vector<int> &nums, int k) {
		// write your code here
		int i=0, j=nums.size()-1;
		while(i<=j){
			if (nums[i]<k) ++i;
			else if (nums[j]>=k) --j;
			else swap(nums[i++],nums[j--]);
		}
		return i;
	}
};
